1. Field of the Invention
The present invention relates to decompression of compressed digital data.
2. Description of the Related Art
Digital data compression systems exist to encode a stream of digital data into compressed digital codes and decode the compressed digital codes back into the original digital data. As the compressed digital codes are defined by fewer bits than the stream of digital data, the data compression system serves to effect a savings in the amount of storage required to hold the digital data and the amount of time required to transmit the digital data. The compression ratio is defined as the ratio of the number of bits used to define the compressed digital codes to the number of bits present in the original digital data. The smaller the compression ratio, the greater will be the savings in storage or time.
One technique for digital data compression is known as the LZW method (or Lempel-Ziv-Welch method), and is described in U.S. Pat. No. 4,558,302. Another technique for digital data compression is known as the GIF (Graphics Interchange Format) method, which is a slight modification of the LZW method. Both the straight LZW and the GIF methods compress a stream of data characters, i.e., character stream, into a stream of codewords, i.e., codestream, by taking advantage of character string repetition in the character stream.
During GIF compression and decompression, a codeword table is dynamically generated. Generally speaking, the codeword table is essentially a dictionary of the codewords present in the codestream. During compression, the codeword table is generated as the character stream is encoded to facilitate encoding of subsequent portions of the character stream. Thus, during compression, the character stream is the input and the codestream is the output, with the codeword table being generated to support provision of the codestream and discarded thereafter. During decompression, the codestream is the input and the character stream is the output, with the codeword table being generated to support provision of the character stream and discarded thereafter. The codeword table does not accompany the codestream. It should be appreciated that in terms of bits, the codestream size is smaller than the character stream size. The ratio of the codestream size to the character stream size is the compression ratio.
During conventional GIF decompression, the codeword table is variable in size. More specifically, the length of a character string associated with a given codeword can vary. The maximum character string length that can be present in the codeword table is a function of the original uncompressed data. For instance, if the original uncompressed data does not include much character repetition, the maximum character string length that will need to be stored in the codeword table may be quite large. Thus, when implementing the conventional GIF decompression method, it is necessary to allocate a substantial amount of memory to storing the codeword table in order to accommodate the maximum anticipated character string length that will need to be stored in the codeword table for any particular codeword. When memory resources are abundant, allocation of a large memory space for storage of the codeword table may not be a problem. Conversely, when memory resources are at a premium, allocation of a large memory space for storage of the codeword may not be possible. Thus, conventional GIF decompression methods may not be easily or reliably implemented in situations where memory resources are limited.
In view of the foregoing, a solution is needed to enable decompression of a GIF codestream in situations where memory limitations may prevent storage of the variable-size codeword table associated with the conventional GIF decompression process.